When a packet communication network becomes congested, ports that supply packets through the communications infrastructure can end up dropping one or more packets in a stream. This can result in errors at the receiving end of a connection. In some networks, however, when a single packet is dropped an entire block of packets may be resent in order to recover from the error. Resending all of the packets in a block in order to recover a single or a few dropped packets adds more traffic and can make the congestion worse.
At the same time, packet traffic is often bursty in that for short time packets will arrive at a port very quickly, then no packets or only a few packets will arrive. In many cases, this bursty pattern is caused by typical user behavior. An Internet browser, for example, might request a web page causing a server to send all of the packets necessary to transfer the web page. The user then views the web page after it is received and makes no requests for a time.
To take advantage of this typical traffic pattern, traffic is throttled at some ports so that during busy periods traffic is buffered and packets are sent at a slower rate than is requested. The extra packets continue to be sent during a normally quiet period until all of the buffers are emptied. This type of throttling requires choices to be made between packets that are urgent or higher priority and those that are less urgent or lower priority. It also requires a scheduler to reduce the rate at which packets are applied to the port in order to prevent any from being dropped. There are many different approaches to scheduling which try to determine which packets should be sent first.
A Round-Robin (RR) and Weighted-Round-Robin (WRR) scheduler picks packets based on a weight assigned to a channel. Bandwidth share is maintained according to weights. Decisions are made on the basis of packets. RR scheduling is used to maintain the relative shares among channels in both non-congested and congested conditions. However, it does not assign a fixed-rate to a channel. This allows any subscriber to use as much bandwidth as is available. Weights can be assigned to channels to give channels different levels of relative shares.
A Deficit-Round-Robin (DRR) scheduler runs in rounds based on a fixed time interval. A channel is added by a certain number of credits or counts in each round. The current number of credits of a channel is the same as the number of bytes or bits the channel is eligible to send. The scheduler picks packets from channels that have enough credits to cover the size of the packet. Traffic is measured in units of bits or bytes rather than in packets, thus DRR maintains bandwidth fairness among channels on the basis of bits-per-second. In contrast, RR and WRR maintain fairness among channels on the basis of the number-of-packets.
With credit-based systems, channels are refilled with credits as time goes by. This changes the round-robin behavior from packet-based scheduling to bandwidth-based scheduling. This also gives the ability for service providers to cap subscriber bandwidths to fixed amounts. Generalized Process Sharing (GPS), Weighted-Fair-Queuing (WFQ), and Worst-Case-Fair-Weighted-Fair-Queuing (WF2Q) are all based on DRR, and are bit-based algorithms.
In a Metro Ethernet Forum (MEF) bandwidth profile, the service requirements for traffic are characterized by a committed information rate (CIR), committed burst size (CBS), an excess information rate (EIR) and an excess burst size (EBS). Each port services subscribers based on the CIR, which defines a minimum rate of traffic forwarding for each channel. The aggregate of all CIRs for the channels of a port is configured to be less than the rate at which the port can service traffic. If port traffic is not fully utilized then the channels of the port can transmit traffic at a rate less than or equal to the EIR, but there is no traffic rate guarantee between the CIR and EIR. For Metro Ethernet systems, the RR and WRR based scheduling can be adapted to schedule selection of packets for transmission through the port by selecting packets based on a weight assigned to a channel to thereby maintain bandwidth share according to these assigned weights. CIR and EIR based traffic scheduling allocates channel weights proportionate to the channel CIR. On each channel a rate limiter is enforced to ensure that no channel exceeds its EIR.